/**********
This library is free software; you can redistribute it and/or modify it under
the terms of the GNU Lesser General Public License as published by the
Free Software Foundation; either version 3 of the License, or (at your
option) any later version. (See <http://www.gnu.org/copyleft/lesser.html>.)

This library is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License for
more details.

You should have received a copy of the GNU Lesser General Public License
along with this library; if not, write to the Free Software Foundation, Inc.,
51 Franklin Street, Fifth Floor, Boston, MA 02110-1301  USA
**********/
// "liveMedia"
// Copyright (c) 1996-2018 Live Networks, Inc.  All rights reserved.
// MP3 internal implementation details (Huffman encoding)
// Implementation

#include "MP3InternalsHuffman.hh"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

MP3HuffmanEncodingInfo
::MP3HuffmanEncodingInfo(Boolean includeDecodedValues) {
    if (includeDecodedValues) {
        decodedValues = new unsigned[(SBLIMIT * SSLIMIT + 1) * 4];
    } else {
        decodedValues = NULL;
    }
}

MP3HuffmanEncodingInfo::~MP3HuffmanEncodingInfo() {
    delete[] decodedValues;
}

// This is crufty old code that needs to be cleaned up #####

static unsigned debugCount = 0; /* for debugging */

#define TRUNC_FAVORa

void updateSideInfoForHuffman(MP3SideInfo &sideInfo, Boolean isMPEG2,
                              unsigned char const *mainDataPtr,
                              unsigned p23L0, unsigned p23L1,
                              unsigned &part23Length0a,
                              unsigned &part23Length0aTruncation,
                              unsigned &part23Length0b,
                              unsigned &part23Length0bTruncation,
                              unsigned &part23Length1a,
                              unsigned &part23Length1aTruncation,
                              unsigned &part23Length1b,
                              unsigned &part23Length1bTruncation) {
    int i, j;
    unsigned sfLength, origTotABsize, adjustment;
    MP3SideInfo::gr_info_s_t *gr;

    /* First, Huffman-decode each part of the segment's main data,
       to see at which bit-boundaries the samples appear:
     */
    MP3HuffmanEncodingInfo hei;

    ++debugCount;
#ifdef DEBUG
    fprintf(stderr, "usifh-start: p23L0: %d, p23L1: %d\n", p23L0, p23L1);
#endif

    /* Process granule 0 */
    {
        gr = &(sideInfo.ch[0].gr[0]);
        origTotABsize = gr->part2_3_length;

        MP3HuffmanDecode(gr, isMPEG2, mainDataPtr, 0, origTotABsize, sfLength, hei);

        /* Begin by computing new sizes for parts a & b (& their truncations) */
#ifdef DEBUG
        fprintf(stderr, "usifh-0: %d, %d:%d, %d:%d, %d:%d, %d:%d, %d:%d\n",
            hei.numSamples,
            sfLength/8, sfLength%8,
            hei.reg1Start/8, hei.reg1Start%8,
            hei.reg2Start/8, hei.reg2Start%8,
            hei.bigvalStart/8, hei.bigvalStart%8,
            origTotABsize/8, origTotABsize%8);
#endif
        if (p23L0 < sfLength) {
            /* We can't use this, so give it all to the next granule: */
            p23L1 += p23L0;
            p23L0 = 0;
        }

        part23Length0a = hei.bigvalStart;
        part23Length0b = origTotABsize - hei.bigvalStart;
        part23Length0aTruncation = part23Length0bTruncation = 0;
        if (origTotABsize > p23L0) {
            /* We need to shorten one or both of fields a & b */
            unsigned truncation = origTotABsize - p23L0;
#ifdef TRUNC_FAIRLY
            part23Length0aTruncation	= (truncation*(part23Length0a-sfLength))
                                    /(origTotABsize-sfLength);
            part23Length0bTruncation = truncation - part23Length0aTruncation;
#endif
#ifdef TRUNC_FAVORa
            part23Length0bTruncation
                    = (truncation > part23Length0b) ? part23Length0b : truncation;
            part23Length0aTruncation = truncation - part23Length0bTruncation;
#endif
#ifdef TRUNC_FAVORb
            part23Length0aTruncation	= (truncation > part23Length0a-sfLength)
          ? (part23Length0a-sfLength) : truncation;
            part23Length0bTruncation = truncation - part23Length0aTruncation;
#endif
        }
        /* ASSERT:  part23Length0xTruncation <= part23Length0x */
        part23Length0a -= part23Length0aTruncation;
        part23Length0b -= part23Length0bTruncation;
#ifdef DEBUG
        fprintf(stderr, "usifh-0: interim sizes: %d (%d), %d (%d)\n",
            part23Length0a, part23Length0aTruncation,
            part23Length0b, part23Length0bTruncation);
#endif

        /* Adjust these new lengths so they end on sample bit boundaries: */
        for (i = 0; i < (int) hei.numSamples; ++i) {
            if (hei.allBitOffsets[i] == part23Length0a) break;
            else if (hei.allBitOffsets[i] > part23Length0a) {
                --i;
                break;
            }
        }
        if (i < 0) { /* should happen only if we couldn't fit sfLength */
            i = 0;
            adjustment = 0;
        } else {
            adjustment = part23Length0a - hei.allBitOffsets[i];
        }
#ifdef DEBUG
        fprintf(stderr, "%d usifh-0: adjustment 1: %d\n", debugCount, adjustment);
#endif
        part23Length0a -= adjustment;
        part23Length0aTruncation += adjustment;
        /* Assign the bits we just shaved to field b and granule 1: */
        if (part23Length0bTruncation < adjustment) {
            p23L1 += (adjustment - part23Length0bTruncation);
            adjustment = part23Length0bTruncation;
        }
        part23Length0b += adjustment;
        part23Length0bTruncation -= adjustment;
        for (j = i; j < (int) hei.numSamples; ++j) {
            if (hei.allBitOffsets[j]
                == part23Length0a + part23Length0aTruncation + part23Length0b)
                break;
            else if (hei.allBitOffsets[j]
                     > part23Length0a + part23Length0aTruncation + part23Length0b) {
                --j;
                break;
            }
        }
        if (j < 0) { /* should happen only if we couldn't fit sfLength */
            j = 0;
            adjustment = 0;
        } else {
            adjustment = part23Length0a + part23Length0aTruncation + part23Length0b
                         - hei.allBitOffsets[j];
        }
#ifdef DEBUG
        fprintf(stderr, "%d usifh-0: adjustment 2: %d\n", debugCount, adjustment);
#endif
        if (adjustment > part23Length0b) adjustment = part23Length0b; /*sanity*/
        part23Length0b -= adjustment;
        part23Length0bTruncation += adjustment;
        /* Assign the bits we just shaved to granule 1 */
        p23L1 += adjustment;

        if (part23Length0aTruncation > 0) {
            /* Change the granule's 'big_values' field to reflect the truncation */
            gr->big_values = i;
        }
    }

    /* Process granule 1 (MPEG-1 only) */

    if (isMPEG2) {
        part23Length1a = part23Length1b = 0;
        part23Length1aTruncation = part23Length1bTruncation = 0;
    } else {
        unsigned granule1Offset
                = origTotABsize + sideInfo.ch[1].gr[0].part2_3_length;

        gr = &(sideInfo.ch[0].gr[1]);
        origTotABsize = gr->part2_3_length;

        MP3HuffmanDecode(gr, isMPEG2, mainDataPtr, granule1Offset,
                         origTotABsize, sfLength, hei);

        /* Begin by computing new sizes for parts a & b (& their truncations) */
#ifdef DEBUG
        fprintf(stderr, "usifh-1: %d, %d:%d, %d:%d, %d:%d, %d:%d, %d:%d\n",
            hei.numSamples,
            sfLength/8, sfLength%8,
            hei.reg1Start/8, hei.reg1Start%8,
            hei.reg2Start/8, hei.reg2Start%8,
            hei.bigvalStart/8, hei.bigvalStart%8,
            origTotABsize/8, origTotABsize%8);
#endif
        if (p23L1 < sfLength) {
            /* We can't use this, so give up on this granule: */
            p23L1 = 0;
        }

        part23Length1a = hei.bigvalStart;
        part23Length1b = origTotABsize - hei.bigvalStart;
        part23Length1aTruncation = part23Length1bTruncation = 0;
        if (origTotABsize > p23L1) {
            /* We need to shorten one or both of fields a & b */
            unsigned truncation = origTotABsize - p23L1;
#ifdef TRUNC_FAIRLY
            part23Length1aTruncation	= (truncation*(part23Length1a-sfLength))
                                    /(origTotABsize-sfLength);
            part23Length1bTruncation = truncation - part23Length1aTruncation;
#endif
#ifdef TRUNC_FAVORa
            part23Length1bTruncation
                    = (truncation > part23Length1b) ? part23Length1b : truncation;
            part23Length1aTruncation = truncation - part23Length1bTruncation;
#endif
#ifdef TRUNC_FAVORb
            part23Length1aTruncation	= (truncation > part23Length1a-sfLength)
          ? (part23Length1a-sfLength) : truncation;
            part23Length1bTruncation = truncation - part23Length1aTruncation;
#endif
        }
        /* ASSERT:  part23Length1xTruncation <= part23Length1x */
        part23Length1a -= part23Length1aTruncation;
        part23Length1b -= part23Length1bTruncation;
#ifdef DEBUG
        fprintf(stderr, "usifh-1: interim sizes: %d (%d), %d (%d)\n",
            part23Length1a, part23Length1aTruncation,
            part23Length1b, part23Length1bTruncation);
#endif

        /* Adjust these new lengths so they end on sample bit boundaries: */
        for (i = 0; i < (int) hei.numSamples; ++i) {
            if (hei.allBitOffsets[i] == part23Length1a) break;
            else if (hei.allBitOffsets[i] > part23Length1a) {
                --i;
                break;
            }
        }
        if (i < 0) { /* should happen only if we couldn't fit sfLength */
            i = 0;
            adjustment = 0;
        } else {
            adjustment = part23Length1a - hei.allBitOffsets[i];
        }
#ifdef DEBUG
        fprintf(stderr, "%d usifh-1: adjustment 0: %d\n", debugCount, adjustment);
#endif
        part23Length1a -= adjustment;
        part23Length1aTruncation += adjustment;
        /* Assign the bits we just shaved to field b: */
        if (part23Length1bTruncation < adjustment) {
            adjustment = part23Length1bTruncation;
        }
        part23Length1b += adjustment;
        part23Length1bTruncation -= adjustment;
        for (j = i; j < (int) hei.numSamples; ++j) {
            if (hei.allBitOffsets[j]
                == part23Length1a + part23Length1aTruncation + part23Length1b)
                break;
            else if (hei.allBitOffsets[j]
                     > part23Length1a + part23Length1aTruncation + part23Length1b) {
                --j;
                break;
            }
        }
        if (j < 0) { /* should happen only if we couldn't fit sfLength */
            j = 0;
            adjustment = 0;
        } else {
            adjustment = part23Length1a + part23Length1aTruncation + part23Length1b
                         - hei.allBitOffsets[j];
        }
#ifdef DEBUG
        fprintf(stderr, "%d usifh-1: adjustment 1: %d\n", debugCount, adjustment);
#endif
        if (adjustment > part23Length1b) adjustment = part23Length1b; /*sanity*/
        part23Length1b -= adjustment;
        part23Length1bTruncation += adjustment;

        if (part23Length1aTruncation > 0) {
            /* Change the granule's 'big_values' field to reflect the truncation */
            gr->big_values = i;
        }
    }
#ifdef DEBUG
    fprintf(stderr, "usifh-end, new vals: %d (%d), %d (%d), %d (%d), %d (%d)\n",
        part23Length0a, part23Length0aTruncation,
        part23Length0b, part23Length0bTruncation,
        part23Length1a, part23Length1aTruncation,
        part23Length1b, part23Length1bTruncation);
#endif
}

static void rsf_getline(char *line, unsigned max, unsigned char **fi) {
    unsigned i;
    for (i = 0; i < max; ++i) {
        line[i] = *(*fi)++;
        if (line[i] == '\n') {
            line[i++] = '\0';
            return;
        }
    }
    line[i] = '\0';
}

static void rsfscanf(unsigned char **fi, unsigned int *v) {
    while (sscanf((char *) *fi, "%x", v) == 0) {
        /* skip past the next '\0' */
        while (*(*fi)++ != '\0') {}
    }

    /* skip past any white-space before the value: */
    while (*(*fi) <= ' ') ++(*fi);

    /* skip past the value: */
    while (*(*fi) > ' ') ++(*fi);
}

#define HUFFBITS unsigned long int
#define SIZEOF_HUFFBITS 4
#define HTN     34
#define MXOFF   250

struct huffcodetab {
    char tablename[3];    /*string, containing table_description	*/
    unsigned int xlen;    /*max. x-index+			      	*/
    unsigned int ylen;    /*max. y-index+				*/
    unsigned int linbits; /*number of linbits			*/
    unsigned int linmax;    /*max number to be stored in linbits	*/
    int ref;        /*a positive value indicates a reference*/
    HUFFBITS *table;    /*pointer to array[xlen][ylen]		*/
    unsigned char *hlen;    /*pointer to array[xlen][ylen]		*/
    unsigned char(*val)[2];/*decoder tree				*/
    unsigned int treelen;    /*length of decoder tree		*/
};

static struct huffcodetab rsf_ht[HTN]; // array of all huffcodetable headers
/* 0..31 Huffman code table 0..31	*/
/* 32,33 count1-tables			*/

/* read the huffman decoder table */
static int read_decoder_table(unsigned char *fi) {
    int n, i, nn, t;
    unsigned int v0, v1;
    char command[100], line[100];
    for (n = 0; n < HTN; n++) {
        rsf_ht[n].table = NULL;
        rsf_ht[n].hlen = NULL;

        /* .table number treelen xlen ylen linbits */
        do {
            rsf_getline(line, 99, &fi);
        } while ((line[0] == '#') || (line[0] < ' '));

        sscanf(line, "%s %s %u %u %u %u", command, rsf_ht[n].tablename,
               &rsf_ht[n].treelen, &rsf_ht[n].xlen, &rsf_ht[n].ylen, &rsf_ht[n].linbits);
        if (strcmp(command, ".end") == 0)
            return n;
        else if (strcmp(command, ".table") != 0) {
#ifdef DEBUG
            fprintf(stderr,"huffman table %u data corrupted\n",n);
#endif
            return -1;
        }
        rsf_ht[n].linmax = (1 << rsf_ht[n].linbits) - 1;

        sscanf(rsf_ht[n].tablename, "%u", &nn);
        if (nn != n) {
#ifdef DEBUG
            fprintf(stderr,"wrong table number %u\n",n);
#endif
            return (-2);
        }
        do {
            rsf_getline(line, 99, &fi);
        } while ((line[0] == '#') || (line[0] < ' '));

        sscanf(line, "%s %u", command, &t);
        if (strcmp(command, ".reference") == 0) {
            rsf_ht[n].ref = t;
            rsf_ht[n].val = rsf_ht[t].val;
            rsf_ht[n].treelen = rsf_ht[t].treelen;
            if ((rsf_ht[n].xlen != rsf_ht[t].xlen) ||
                (rsf_ht[n].ylen != rsf_ht[t].ylen)) {
#ifdef DEBUG
                fprintf(stderr,"wrong table %u reference\n",n);
#endif
                return (-3);
            };
            while ((line[0] == '#') || (line[0] < ' ')) {
                rsf_getline(line, 99, &fi);
            }
        } else if (strcmp(command, ".treedata") == 0) {
            rsf_ht[n].ref = -1;
            rsf_ht[n].val = (unsigned char (*)[2])
                    new unsigned char[2 * (rsf_ht[n].treelen)];
            if ((rsf_ht[n].val == NULL) && (rsf_ht[n].treelen != 0)) {
#ifdef DEBUG
                fprintf(stderr, "heaperror at table %d\n",n);
#endif
                return -1;
            }
            for (i = 0; (unsigned) i < rsf_ht[n].treelen; i++) {
                rsfscanf(&fi, &v0);
                rsfscanf(&fi, &v1);
/*replaces        fscanf(fi,"%x %x",&v0, &v1);*/
                rsf_ht[n].val[i][0] = (unsigned char) v0;
                rsf_ht[n].val[i][1] = (unsigned char) v1;
            }
            rsf_getline(line, 99, &fi); /* read the rest of the line */
        } else {
#ifdef DEBUG
            fprintf(stderr,"huffman decodertable error at table %d\n",n);
#endif
        }
    }
    return n;
}

static void initialize_huffman() {
    static Boolean huffman_initialized = False;

    if (huffman_initialized) return;

    if (read_decoder_table(huffdec) != HTN) {
#ifdef DEBUG
        fprintf(stderr,"decoder table read error\n");
#endif
        return;
    }
    huffman_initialized = True;
}

static unsigned char const slen[2][16] = {
        {0, 0, 0, 0, 3, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4},
        {0, 1, 2, 3, 0, 1, 2, 3, 1, 2, 3, 1, 2, 3, 2, 3}
};

static unsigned char const stab[3][6][4] = {
        {{6, 5, 5, 5}, {6, 5, 7,  3}, {11, 10, 0, 0},
                {7,  7,  7,  0}, {6,  6,  6, 3}, {8,  8,  5, 0}},
        {{9, 9, 9, 9}, {9, 9, 12, 6}, {18, 18, 0, 0},
                {12, 12, 12, 0}, {12, 9,  9, 6}, {15, 12, 9, 0}},
        {{6, 9, 9, 9}, {6, 9, 12, 6}, {15, 18, 0, 0},
                {6,  15, 12, 0}, {6,  12, 9, 6}, {6,  18, 9, 0}}
};

static unsigned rsf_get_scale_factors_1(MP3SideInfo::gr_info_s_t *gr_info) {
    int numbits;
    int num0 = slen[0][gr_info->scalefac_compress];
    int num1 = slen[1][gr_info->scalefac_compress];

    if (gr_info->block_type == 2) {
        numbits = (num0 + num1) * 18;

        if (gr_info->mixed_block_flag) {
            numbits -= num0; /* num0 * 17 + num1 * 18 */
        }
    } else {
        int scfsi = gr_info->scfsi;

        if (scfsi < 0) { /* scfsi < 0 => granule == 0 */
            numbits = (num0 + num1) * 10 + num0;
        } else {
            numbits = 0;
            if (!(scfsi & 0x8)) {
                numbits += num0 * 6;
            } else {
            }

            if (!(scfsi & 0x4)) {
                numbits += num0 * 5;
            } else {
            }

            if (!(scfsi & 0x2)) {
                numbits += num1 * 5;
            } else {
            }

            if (!(scfsi & 0x1)) {
                numbits += num1 * 5;
            } else {
            }
        }
    }

    return numbits;
}

extern unsigned n_slen2[];
extern unsigned i_slen2[];

static unsigned rsf_get_scale_factors_2(MP3SideInfo::gr_info_s_t *gr_info) {
    unsigned char const *pnt;
    int i;
    unsigned int slen;
    int n = 0;
    int numbits = 0;

    slen = n_slen2[gr_info->scalefac_compress];

    gr_info->preflag = (slen >> 15) & 0x1;

    n = 0;
    if (gr_info->block_type == 2) {
        n++;
        if (gr_info->mixed_block_flag)
            n++;
    }

    pnt = stab[n][(slen >> 12) & 0x7];

    for (i = 0; i < 4; i++) {
        int num = slen & 0x7;
        slen >>= 3;
        numbits += pnt[i] * num;
    }

    return numbits;
}

static unsigned getScaleFactorsLength(MP3SideInfo::gr_info_s_t *gr,
                                      Boolean isMPEG2) {
    return isMPEG2 ? rsf_get_scale_factors_2(gr)
                   : rsf_get_scale_factors_1(gr);
}

static int rsf_huffman_decoder(BitVector &bv,
                               struct huffcodetab const *h,
                               int *x, int *y, int *v, int *w); // forward

void MP3HuffmanDecode(MP3SideInfo::gr_info_s_t *gr, Boolean isMPEG2,
                      unsigned char const *fromBasePtr,
                      unsigned fromBitOffset, unsigned fromLength,
                      unsigned &scaleFactorsLength,
                      MP3HuffmanEncodingInfo &hei) {
    unsigned i;
    int x, y, v, w;
    struct huffcodetab *h;
    BitVector bv((unsigned char *) fromBasePtr, fromBitOffset, fromLength);

    /* Compute the size of the scale factors (& also advance bv): */
    scaleFactorsLength = getScaleFactorsLength(gr, isMPEG2);
    bv.skipBits(scaleFactorsLength);

    initialize_huffman();

    hei.reg1Start = hei.reg2Start = hei.numSamples = 0;

    /* Read bigvalues area. */
    if (gr->big_values < gr->region1start + gr->region2start) {
        gr->big_values = gr->region1start + gr->region2start; /* sanity check */
    }
    for (i = 0; i < gr->big_values; ++i) {
        if (i < gr->region1start) {
            /* in region 0 */
            h = &rsf_ht[gr->table_select[0]];
        } else if (i < gr->region2start) {
            /* in region 1 */
            h = &rsf_ht[gr->table_select[1]];
            if (hei.reg1Start == 0) {
                hei.reg1Start = bv.curBitIndex();
            }
        } else {
            /* in region 2 */
            h = &rsf_ht[gr->table_select[2]];
            if (hei.reg2Start == 0) {
                hei.reg2Start = bv.curBitIndex();
            }
        }

        hei.allBitOffsets[i] = bv.curBitIndex();
        rsf_huffman_decoder(bv, h, &x, &y, &v, &w);
        if (hei.decodedValues != NULL) {
            // Record the decoded values:
            unsigned *ptr = &hei.decodedValues[4 * i];
            ptr[0] = x;
            ptr[1] = y;
            ptr[2] = v;
            ptr[3] = w;
        }
    }
    hei.bigvalStart = bv.curBitIndex();

    /* Read count1 area. */
    h = &rsf_ht[gr->count1table_select + 32];
    while (bv.curBitIndex() < bv.totNumBits() && i < SSLIMIT * SBLIMIT) {
        hei.allBitOffsets[i] = bv.curBitIndex();
        rsf_huffman_decoder(bv, h, &x, &y, &v, &w);
        if (hei.decodedValues != NULL) {
            // Record the decoded values:
            unsigned *ptr = &hei.decodedValues[4 * i];
            ptr[0] = x;
            ptr[1] = y;
            ptr[2] = v;
            ptr[3] = w;
        }
        ++i;
    }

    hei.allBitOffsets[i] = bv.curBitIndex();
    hei.numSamples = i;
}

HUFFBITS dmask = 1 << (SIZEOF_HUFFBITS * 8 - 1);
unsigned int hs = SIZEOF_HUFFBITS * 8;

/* do the huffman-decoding 						*/
static int rsf_huffman_decoder(BitVector &bv,
                               struct huffcodetab const *h, // ptr to huffman code record
        /* unsigned */ int *x, // returns decoded x value
        /* unsigned */ int *y,  // returns decoded y value
                               int *v, int *w) {
    HUFFBITS level;
    unsigned point = 0;
    int error = 1;
    level = dmask;
    *x = *y = *v = *w = 0;
    if (h->val == NULL) return 2;

    /* table 0 needs no bits */
    if (h->treelen == 0) return 0;

    /* Lookup in Huffman table. */

    do {
        if (h->val[point][0] == 0) {   /*end of tree*/
            *x = h->val[point][1] >> 4;
            *y = h->val[point][1] & 0xf;

            error = 0;
            break;
        }
        if (bv.get1Bit()) {
            while (h->val[point][1] >= MXOFF) point += h->val[point][1];
            point += h->val[point][1];
        } else {
            while (h->val[point][0] >= MXOFF) point += h->val[point][0];
            point += h->val[point][0];
        }
        level >>= 1;
    } while (level || (point < h->treelen));
/////  } while (level  || (point < rsf_ht->treelen) );

    /* Check for error. */

    if (error) { /* set x and y to a medium value as a simple concealment */
        printf("Illegal Huffman code in data.\n");
        *x = ((h->xlen - 1) << 1);
        *y = ((h->ylen - 1) << 1);
    }

    /* Process sign encodings for quadruples tables. */

    if (h->tablename[0] == '3'
        && (h->tablename[1] == '2' || h->tablename[1] == '3')) {
        *v = (*y >> 3) & 1;
        *w = (*y >> 2) & 1;
        *x = (*y >> 1) & 1;
        *y = *y & 1;

        if (*v)
            if (bv.get1Bit() == 1) *v = -*v;
        if (*w)
            if (bv.get1Bit() == 1) *w = -*w;
        if (*x)
            if (bv.get1Bit() == 1) *x = -*x;
        if (*y)
            if (bv.get1Bit() == 1) *y = -*y;
    }

        /* Process sign and escape encodings for dual tables. */

    else {
        if (h->linbits)
            if ((h->xlen - 1) == (unsigned) *x)
                *x += bv.getBits(h->linbits);
        if (*x)
            if (bv.get1Bit() == 1) *x = -*x;
        if (h->linbits)
            if ((h->ylen - 1) == (unsigned) *y)
                *y += bv.getBits(h->linbits);
        if (*y)
            if (bv.get1Bit() == 1) *y = -*y;
    }

    return error;
}

#ifdef DO_HUFFMAN_ENCODING
inline int getNextSample(unsigned char const*& fromPtr) {
  int sample
#ifdef FOUR_BYTE_SAMPLES
    = (fromPtr[0]<<24) | (fromPtr[1]<<16) | (fromPtr[2]<<8) | fromPtr[3];
#else
#ifdef TWO_BYTE_SAMPLES
    = (fromPtr[0]<<8) | fromPtr[1];
#else
    // ONE_BYTE_SAMPLES
    = fromPtr[0];
#endif
#endif
  fromPtr += BYTES_PER_SAMPLE_VALUE;
  return sample;
}

static void rsf_huffman_encoder(BitVector& bv,
                struct huffcodetab* h,
                int x, int y, int v, int w); // forward

unsigned MP3HuffmanEncode(MP3SideInfo::gr_info_s_t const* gr,
              unsigned char const* fromPtr,
              unsigned char* toPtr, unsigned toBitOffset,
              unsigned numHuffBits) {
   unsigned i;
   struct huffcodetab *h;
   int x, y, v, w;
   BitVector bv(toPtr, toBitOffset, numHuffBits);

   initialize_huffman();

   // Encode big_values area:
   unsigned big_values = gr->big_values;
   if (big_values < gr->region1start + gr->region2start) {
     big_values = gr->region1start + gr->region2start; /* sanity check */
   }
   for (i = 0; i < big_values; ++i) {
     if (i < gr->region1start) {
       /* in region 0 */
       h = &rsf_ht[gr->table_select[0]];
     } else if (i < gr->region2start) {
       /* in region 1 */
       h = &rsf_ht[gr->table_select[1]];
     } else {
       /* in region 2 */
       h = &rsf_ht[gr->table_select[2]];
     }

     x = getNextSample(fromPtr);
     y = getNextSample(fromPtr);
     v = getNextSample(fromPtr);
     w = getNextSample(fromPtr);
     rsf_huffman_encoder(bv, h, x, y, v, w);
   }

   // Encode count1 area:
   h = &rsf_ht[gr->count1table_select+32];
   while (bv.curBitIndex() < bv.totNumBits() &&  i < SSLIMIT*SBLIMIT) {
     x = getNextSample(fromPtr);
     y = getNextSample(fromPtr);
     v = getNextSample(fromPtr);
     w = getNextSample(fromPtr);
     rsf_huffman_encoder(bv, h, x, y, v, w);
     ++i;
   }

   return i;
}

static Boolean lookupHuffmanTableEntry(struct huffcodetab const* h,
                       HUFFBITS bits, unsigned bitsLength,
                       unsigned char& xy) {
  unsigned point = 0;
  unsigned mask = 1;
  unsigned numBitsTestedSoFar = 0;
  do {
    if (h->val[point][0]==0) { // end of tree
      xy = h->val[point][1];
      if (h->hlen[xy] == 0) { // this entry hasn't already been used
    h->table[xy] = bits;
    h->hlen[xy] = bitsLength;
    return True;
      } else { // this entry has already been seen
    return False;
      }
    }

    if (numBitsTestedSoFar++ == bitsLength) {
      // We don't yet have enough bits for this prefix
      return False;
    }
    if (bits&mask) {
      while (h->val[point][1] >= MXOFF) point += h->val[point][1];
      point += h->val[point][1];
    } else {
      while (h->val[point][0] >= MXOFF) point += h->val[point][0];
      point += h->val[point][0];
    }
    mask <<= 1;
  } while (mask || (point < h->treelen));

  return False;
}

static void buildHuffmanEncodingTable(struct huffcodetab* h) {
  h->table = new unsigned long[256];
  h->hlen = new unsigned char[256];
  if (h->table == NULL || h->hlen == NULL) { h->table = NULL; return; }
  for (unsigned i = 0; i < 256; ++i) {
    h->table[i] = 0; h->hlen[i] = 0;
  }

  // Look up entries for each possible bit sequence length:
  unsigned maxNumEntries = h->xlen * h->ylen;
  unsigned numEntries = 0;
  unsigned powerOf2 = 1;
  for (unsigned bitsLength = 1;
       bitsLength <= 8*SIZEOF_HUFFBITS; ++bitsLength) {
    powerOf2 *= 2;
    for (HUFFBITS bits = 0; bits < powerOf2; ++bits) {
      // Find the table value - if any - for 'bits' (length 'bitsLength'):
      unsigned char xy;
      if (lookupHuffmanTableEntry(h, bits, bitsLength, xy)) {
    ++numEntries;
    if (numEntries == maxNumEntries) return; // we're done
      }
    }
  }
#ifdef DEBUG
  fprintf(stderr, "Didn't find enough entries!\n"); // shouldn't happen
#endif
}

static void lookupXYandPutBits(BitVector& bv, struct huffcodetab const* h,
                   unsigned char xy) {
  HUFFBITS bits = h->table[xy];
  unsigned bitsLength = h->hlen[xy];

  // Note that "bits" is in reverse order, so read them from right-to-left:
  while (bitsLength-- > 0) {
    bv.put1Bit(bits&0x00000001);
    bits >>= 1;
  }
}

static void putLinbits(BitVector& bv, struct huffcodetab const* h,
               HUFFBITS bits) {
  bv.putBits(bits, h->linbits);
}

static void rsf_huffman_encoder(BitVector& bv,
                struct huffcodetab* h,
                int x, int y, int v, int w) {
  if (h->val == NULL) return;

  /* table 0 produces no bits */
  if (h->treelen == 0) return;

  if (h->table == NULL) {
    // We haven't yet built the encoding array for this table; do it now:
    buildHuffmanEncodingTable(h);
    if (h->table == NULL) return;
  }

  Boolean xIsNeg = False, yIsNeg = False, vIsNeg = False, wIsNeg = False;
  unsigned char xy;

#ifdef FOUR_BYTE_SAMPLES
#else
#ifdef TWO_BYTE_SAMPLES
  // Convert 2-byte negative numbers to their 4-byte equivalents:
  if (x&0x8000) x |= 0xFFFF0000;
  if (y&0x8000) y |= 0xFFFF0000;
  if (v&0x8000) v |= 0xFFFF0000;
  if (w&0x8000) w |= 0xFFFF0000;
#else
  // ONE_BYTE_SAMPLES
  // Convert 1-byte negative numbers to their 4-byte equivalents:
  if (x&0x80) x |= 0xFFFFFF00;
  if (y&0x80) y |= 0xFFFFFF00;
  if (v&0x80) v |= 0xFFFFFF00;
  if (w&0x80) w |= 0xFFFFFF00;
#endif
#endif

  if (h->tablename[0] == '3'
      && (h->tablename[1] == '2' || h->tablename[1] == '3')) {// quad tables
    if (x < 0) { xIsNeg = True; x = -x; }
    if (y < 0) { yIsNeg = True; y = -y; }
    if (v < 0) { vIsNeg = True; v = -v; }
    if (w < 0) { wIsNeg = True; w = -w; }

    // Sanity check: x,y,v,w must all be 0 or 1:
    if (x>1 || y>1 || v>1 || w>1) {
#ifdef DEBUG
      fprintf(stderr, "rsf_huffman_encoder quad sanity check fails: %x,%x,%x,%x\n", x, y, v, w);
#endif
    }

    xy = (v<<3)|(w<<2)|(x<<1)|y;
    lookupXYandPutBits(bv, h, xy);

    if (v) bv.put1Bit(vIsNeg);
    if (w) bv.put1Bit(wIsNeg);
    if (x) bv.put1Bit(xIsNeg);
    if (y) bv.put1Bit(yIsNeg);
  } else { // dual tables
    // Sanity check: v and w must be 0:
    if (v != 0 || w != 0) {
#ifdef DEBUG
      fprintf(stderr, "rsf_huffman_encoder dual sanity check 1 fails: %x,%x,%x,%x\n", x, y, v, w);
#endif
    }

    if (x < 0) { xIsNeg = True; x = -x; }
    if (y < 0) { yIsNeg = True; y = -y; }

    // Sanity check: x and y must be <= 255:
    if (x > 255 || y > 255) {
#ifdef DEBUG
      fprintf(stderr, "rsf_huffman_encoder dual sanity check 2 fails: %x,%x,%x,%x\n", x, y, v, w);
#endif
    }

    int xl1 = h->xlen-1;
    int yl1 = h->ylen-1;
    unsigned linbitsX = 0; unsigned linbitsY = 0;

    if (((x < xl1) || (xl1 == 0)) && (y < yl1)) {
      // normal case
      xy = (x<<4)|y;
      lookupXYandPutBits(bv, h, xy);
      if (x) bv.put1Bit(xIsNeg);
      if (y) bv.put1Bit(yIsNeg);
    } else if (x >= xl1) {
      linbitsX = (unsigned)(x - xl1);
      if (linbitsX > h->linmax) {
#ifdef DEBUG
    fprintf(stderr,"warning: Huffman X table overflow\n");
#endif
    linbitsX = h->linmax;
      };

      if (y >= yl1) {
    xy = (xl1<<4)|yl1;
    lookupXYandPutBits(bv, h, xy);
    linbitsY = (unsigned)(y - yl1);
    if (linbitsY > h->linmax) {
#ifdef DEBUG
      fprintf(stderr,"warning: Huffman Y table overflow\n");
#endif
      linbitsY = h->linmax;
    };

    if (h->linbits) putLinbits(bv, h, linbitsX);
    if (x) bv.put1Bit(xIsNeg);
    if (h->linbits) putLinbits(bv, h, linbitsY);
    if (y) bv.put1Bit(yIsNeg);
      } else { /* x >= h->xlen, y < h->ylen */
    xy = (xl1<<4)|y;
    lookupXYandPutBits(bv, h, xy);
    if (h->linbits) putLinbits(bv, h, linbitsX);
    if (x) bv.put1Bit(xIsNeg);
    if (y) bv.put1Bit(yIsNeg);
      }
    } else { /* ((x < h->xlen) && (y >= h->ylen)) */
      xy = (x<<4)|yl1;
      lookupXYandPutBits(bv, h, xy);
      linbitsY = y-yl1;
      if (linbitsY > h->linmax) {
#ifdef DEBUG
    fprintf(stderr,"warning: Huffman Y table overflow\n");
#endif
    linbitsY = h->linmax;
      };
      if (x) bv.put1Bit(xIsNeg);
      if (h->linbits) putLinbits(bv, h, linbitsY);
      if (y) bv.put1Bit(yIsNeg);
    }
  }
}
#endif
